# 80. 删除有序数组中的重复项 II
# 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
# 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
def removeDuplicates(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    slow_index = 0
    fast_index = 1
    # 元素出现的次数
    repeat_count = 1
    while fast_index < len(nums):
        if nums[slow_index] == nums[fast_index]:
            nums[slow_index + repeat_count] = nums[fast_index]
            repeat_count += 1
            fast_index += 1
        else:
            if repeat_count > 1:
                slow_index += 2
            else:
                slow_index += 1
            nums[slow_index] = nums[fast_index]
            fast_index += 1
            repeat_count = 1

        if repeat_count > 2:
            repeat_count = 2

    return slow_index + repeat_count


def removeDuplicatesShort(nums):
    # 从第k个元素开始遍历
    # 通用解法
    def common_solve(k):
        # k位置前面的元素，是不会发生变化的
        result_index = k
        # 从第k个元素开始判断
        for num in nums[k:]:
            # 判断【当前元素】和【当前元素往前挪k个位置的元素】是否不相等
            # 1）如果相等，当前元素需要被移除，继续查找下一个元素
            # 2）如果不相等，当前元素不能被移除
            if nums[result_index - k] != num:
                nums[result_index] = num
                result_index += 1
        return result_index
    # 重复的元素只能出现2个
    return common_solve(2)


nums_1 = [1, 2, 2, 2, 2, 3, 3, 3, 4, 5, 7, 8, 8]

print(f"removeDuplicates before nums_1:{nums_1}")
result = removeDuplicatesShort(nums_1)
print(f"removeDuplicates after nums_1:{nums_1} , result:{result}")

nums_1 = [2, 2, 2]

print(f"removeDuplicates before nums_1:{nums_1}")
result = removeDuplicatesShort(nums_1)
print(f"removeDuplicates after nums_1:{nums_1} , result:{result}")

nums_1 = [2, 2, 2, 2]

print(f"removeDuplicates before nums_1:{nums_1}")
result = removeDuplicatesShort(nums_1)
print(f"removeDuplicates after nums_1:{nums_1} , result:{result}")

nums_1 = [1, 2, 2, 2, 2]

print(f"removeDuplicates before nums_1:{nums_1}")
result = removeDuplicatesShort(nums_1)
print(f"removeDuplicates after nums_1:{nums_1} , result:{result}")
